# https://leetcode-cn.com/problems/longest-common-prefix/
from typing import List
class Solution:

    def longestCommonPrefix(self, strs: List[str]) -> str:
        """水平扫描，不用遍历所有元素，只需要比较最大和最小元素"""
        if not strs:
            return ''
        s1 = min(strs)
        s2 = max(strs)
        if s1 == s2:
            # 这里是从前往后找，防止s1和s2是一样的，浪费时间，逻辑上没问题
            # 包含只有一个元素，以及所有元素都一样
            return s1
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                return s1[:i]
        return s1

    def commonPrefix(self, s1: str, s2: str) -> str:
        """水平扫描，从后往前。否则会有效率问题"""
        leng = min(len(s1), len(s2))
        for i in range(leng):
            if s1[:leng-i] == s2[:leng-i]:
                return s1[:leng-i]
        return ''


    def longestCommonPrefix2(self, strs: List[str]) -> str:
        """二分查找，只有在字符串很长上百了才会有优势"""
        if not strs:
            return ''
        s1 = min(strs)
        s2 = max(strs)
        if s1 == s2:
            # 包含只有一个元素，以及所有元素都一样
            return s1
        left = 0
        right = len(s1) - 1
        mid = (left + right) // 2
        while left < right:
            if s1[:mid+1] == s2[:mid+1]:
                left = mid + 1
            else:
                right = mid - 1
            mid = (left + right) // 2
        return s1[:mid+1] if s1[:mid+1] == s2[:mid+1] else s1[:mid]


    def longestCommonPrefix3(self, strs: List[str]) -> str:
        """垂直查找"""
        if len(strs) == 0:
            return ''
        if '' in strs:
            return ''
        if len(strs) == 1:
            return strs[0]

        res = ''
        for i in range(1, len(strs[0])+1):
            res = strs[0][:i]
            for s in strs[1:]:
                if not s.startswith(res):
                    return res[:-1]
        else:
            return res

    def longestCommonPrefix4(self, strs: List[str]) -> str:
        """代码简洁，逻辑清晰。都是内置函数，效率也不差"""
        s = ""
        for i in zip(*strs):
            if len(set(i)) == 1:
                s += i[0]
            else:
                break           
        return s


if __name__ == "__main__":
    strs = ["abc","abcd"]
    res = Solution().longestCommonPrefix(strs)
    print(res)
